package program;

/**
 * 输入两个正整数m和n 求他们的最大公约数和最小公倍数
 * <p>
 * 最大公约数
 * 在循环中，只要除数不等于0，用较大的数除以较小的数，将小的一个数作为下一轮循环的大数，
 * 取得的余数作为下一轮循环较小的数，如此循环直到较小的数值为0，返回较大的数。即为最大公约数。
 * <p>
 * 辗转相除法（欧几里得算法）
 * 定理：两个整数的最大公约数等于其中较小的那个数和两数的相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。
 * <p>
 * 最小公倍数 = (m * n)/最大公约数
 *
 * @author luxx
 * @date 2018/4/27 0027
 */
public class CommonDivisor {

    public static void commonDivisor(int m, int n) {
        int i = m;
        int j = n;
        int temp1, temp2;
        //排序 把小的数赋值为n
        if (m < n) {
            temp1 = n;
            n = m;
            m = temp1;
        }
        //把大小数取余 取得的余数作为下一轮循环较小的数，如此循环直到较小的数值为0，返回较大的数。即为最大公约数。
        while (n != 0) {
            temp2 = m % n;
            m = n;
            n = temp2;
        }
        //最小公倍数
        int t = i * j / m;
        System.out.println(i + "和" + j + "的最大公约数为：" + m);
        System.out.println(i + "和" + j + "的最小公倍数为：" + t);
    }

    public static void main(String[] args) {

        commonDivisor(20, 30);
    }
}